package basic_datastructure.heap;

import java.util.Arrays;

/**
 * 利用最大堆实现最大优先队列
 */
public class PriorityQueue {
    private int[] array;
    private int size;

    public PriorityQueue() {
        //队列初始长度为32
        array = new int[32];
    }

    /**
     * 入队
     *
     * @param key 入队元素
     */
    public void enQueue(int key) {
        //如果超出队列长度，扩容
        if (size >= array.length) {
            resize();
        }
        //入队元素的位置是数组的最后一位
        array[size++] = key;
        //调整到合适的位置
        upAdjust();
    }

    /**
     * 出队
     *
     * @throws Exception 队列为空
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("the queue is empty!");
        }
        //出队元素为堆顶元素
        int res = array[0];
        //让最后一个元素移动到堆顶
        array[0] = array[--size];
        //调增成新的最大堆
        downAdjust();
        return res;
    }

    /**
     * 上浮调整
     */
    public void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        while (childIndex > 0 && array[childIndex] > array[parentIndex]) {
            swap(array, childIndex, parentIndex);
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
    }

    /**
     * 下沉调整
     */
    public void downAdjust() {
        int parentIndex = 0;
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < size) {
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            if (array[parentIndex] >= array[childIndex]) {
                break;
            }
            swap(array, childIndex, parentIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }

    /**
     * 队列扩容
     */
    private void resize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(array, newSize);
    }

    /**
     * 交换
     */
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(12131);
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
    }
}
